How to do binary search step by step?

2024-07-08 18:08| 来源: 网络整理| 查看: 265

Binary search is an efficient search algorithm that works on sorted arrays or lists. It repeatedly divides the search space in half until the target element is found or the search space is exhausted.

Step-by-Step Guide to Perform Binary Search: Step 1: Initialize Variables low: Set this variable to 0, representing the lower bound of the search space. high: Set this variable to the length of the array minus 1, representing the upper bound of the search space. target: This is the element you are searching for in the array. Step 2: Calculate Midpoint Find the midpoint of the current search space using the formula: mid = (low + high) / 2. Step 3: Compare Midpoint to Target If array[mid] == target, you have found the target element. Return the index mid. If array[mid] < target, the target element must be in the right half of the search space. Set low = mid + 1. If array[mid] > target, the target element must be in the left half of the search space. Set high = mid – 1. Step 4: Repeat Steps 2-3 Repeat steps 2 and 3 until either the target element is found or low > high. Step 5: Return Result If the target element was found, return the index mid. If the target element was not found, return -1 to indicate that the element is not present in the array. Illustration of Binary Search Algorithm:

Consider the sorted array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

To find the target element 11:

Step 1: Initialize pointers

left = 0 (start of array) right = 9 (end of array)

Step 2: Calculate midpoint

mid = (left + right) / 2 = (0 + 9) / 2 = 4

Step 3: Compare target with midpoint

target = 11 array[mid] = 9

Since target is greater than array[mid], search in the right half.

Step 4: Update pointers based on Step 3

left = mid + 1 = 5

Step 5: Repeat steps 2-4

mid = (left + right) / 2 = (5 + 9) / 2 = 7 array[mid] = 15 array[mid] > target, then search in the left half. right = mid – 1 = 6 mid = (left + right) / 2 = (5 + 6) / 2 = 5 array[mid] = 11

Step 6: Target found

array[mid] == target, we have found the target element. Return the index mid. Conclusion:

Binary search is a powerful algorithm for efficiently searching sorted arrays or lists. By repeatedly dividing the search space in half, it can quickly locate the target element or determine that it is not present.

tarunsarawgi_gfg Improve Next Article C Program for Binary Search Tree Please Login to comment...

【本文地址】

公司简介

联系我们